package erfgame.core.path;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;


import erfgame.core.dao.ObjectDAO;
import erfgame.core.entity.Entity;
import erfgame.core.world.World;
import erfgame.core.world.WorldContext;
import erfgame.core.world.WorldDAOManager;
import erfgame.core.world.terrain.BlockGridTiles;
import erfgame.core.world.terrain.GridTile;
import erfgame.core.world.terrain.TerrainUtils;
import erfgame.core.world.terrain.WalkablePath;

public class AStarPathCalculator implements PathCalculator {

	private WorldDAOManager worldDAOManager;
	private WorldContext worldContext;
	private Coster coster;
	private CostEstimator estimator;
	
	public AStarPathCalculator( 
			WorldDAOManager worldDAOManager,
			WorldContext worldContext, 
			Coster coster, 
			CostEstimator estimator 
	) {
		this.worldDAOManager = worldDAOManager;
		this.worldContext = worldContext;
		this.coster = coster;
		this.estimator = estimator;
	}
	
	public List<PathElement> calculatePath( 
			Entity client,
			int gxFrom, int gyFrom, int gIndexFrom, 
			int gxTo, int gyTo, int gIndexTo,
			int bx, int by, int bw, int bh ) {
		World world = worldContext.getCurrentWorld();
		ObjectDAO<Point,BlockGridTiles> gridTilesDAO = worldDAOManager.getGridTilesDAO(world);
		
		int gridsX = world.getXGridTilesPerBlock();
		int gridsY = world.getYGridTilesPerBlock();
		
		int mingx = bx * gridsX;
		int mingy = by * gridsY;
		int maxgx = (bx + bw) * gridsX - 1;
		int maxgy = (by + bh) * gridsY - 1;
		
		int setSize = Math.abs( gxFrom - gxTo ) + Math.abs( gyFrom - gyTo );
		HashSet<Node> closedSet = new HashSet<Node>( setSize );
		ArrayList<Node> openList = new ArrayList<Node>( setSize );
		
		int startEstimate = this.estimator.estimate(gxFrom, gyFrom, gIndexFrom, gxTo, gyTo, gIndexTo);
		
		Node startNode = new Node( 0, startEstimate, gxFrom, gyFrom, gIndexFrom );
		openList.add( startNode );
		
		Point directionResult = new Point();
		
		while( !openList.isEmpty() ) {
			Node currentNode = openList.remove(openList.size() - 1);
			int gx = currentNode.gx;
			int gy = currentNode.gy;
			int gIndex = currentNode.gIndex;
			if( gx == gxTo && gy == gyTo && gIndex == gIndexTo ) {
				return reconstructPath( currentNode );
			}
			closedSet.add( currentNode );
			// get adjacent nodes to current node
			int gbx = gx >> world.getxGridTilesPerBlockShift();
			int gby = gy >> world.getyGridTilesPerBlockShift();
			
			int localgx = gx & world.getxGridTilesPerBlockMask();
			int localgy = gy & world.getyGridTilesPerBlockMask();

			// TODO : maintain previous block as it's probably going to be the same
			
			BlockGridTiles tiles = gridTilesDAO.retrieveObject( new Point( gbx, gby ) );
			GridTile gridTile = tiles.getGridTile( localgx, localgy, gIndex );
			int[][] pathIndexes = gridTile.getPathIndexes();
			for( int direction=pathIndexes.length; direction>0; ) {
				direction--;
				int[] directionPathIndexes = pathIndexes[direction];
				TerrainUtils.getGridCoordinates(gx, gy, direction, directionResult);
				int ngx = directionResult.x;
				int ngy = directionResult.y;
				if( ngx >= mingx && ngy >= mingy && ngx <= maxgx && ngy <= maxgy ) {
					TerrainUtils.getPathCoordinates(gx, gy, direction, directionResult);
					int px = directionResult.x;
					int py = directionResult.y;
					
					int pbx = px >> world.getXPathTilesPerBlockShift();
					int pby = py >> world.getYPathTilesPerBlockShift();
					BlockGridTiles pathTiles;
					if( pbx != gbx || pby != gby ) {
						pathTiles = gridTilesDAO.retrieveObject( new Point(pbx, pby) );
					} else {
						pathTiles = tiles;
					}
					
					int localpx = px & world.getXPathTilesPerBlockMask();
					int localpy = py & world.getYPathTilesPerBlockMask();
					WalkablePath[] paths = pathTiles.getPaths(localpx, localpy);
					for( int i=directionPathIndexes.length; i>0; ) {
						i--;
						int pathIndex = directionPathIndexes[i];
						WalkablePath path = paths[pathIndex];
						int cost = coster.getCost(client, px, py, pathIndex, path);
						if( cost > 0 ) {
							int targetGridIndex;
							switch( direction ) {
							case BlockGridTiles.INDEX_NE:
							case BlockGridTiles.INDEX_SE:
								targetGridIndex = path.getToGridIndex();
								break;
							default:
								targetGridIndex = path.getFromGridIndex();
								break;
							}
							Node newNode = new Node(
									currentNode.costSoFar + cost, 
									0, 
									ngx, ngy, targetGridIndex
							);
							if( !closedSet.contains( newNode ) ) {
								int estimate = estimator.estimate(ngx, ngy, targetGridIndex, gxTo, gyTo, gIndexTo);
								newNode.estimatedCostRemaining = estimate;
								
								// TODO : linear search, makes algorithm much slower (use two sorted array lists? a map and a list?)
								int existingIndex = openList.indexOf( newNode );
								boolean valid;
								if( existingIndex >= 0 ) {
									Node existingNode = openList.get( existingIndex );
									valid = newNode.getTotalEstimatedCost() < existingNode.getTotalEstimatedCost();
									if( valid ) {
										openList.remove( existingIndex );
									}
								} else {
									valid = true;
								}
								if( valid ) {
									int newIndex = Collections.binarySearch(openList, newNode);
									if( newIndex < 0 ) {
										newIndex = -(newIndex+1);
									}
									newNode.fromDirection = direction;
									newNode.fromNode = currentNode;
									newNode.fromPathIndex = pathIndex;
									newNode.fromPathX = px;
									newNode.fromPathY = py;
									newNode.steps = currentNode.steps + 1;
									openList.add( newIndex, newNode );
								}
							}
						}
					}
				}
			}
		}
		return null;
	}
	
	private final List<PathElement> reconstructPath( Node node ) {
		
		ArrayList<PathElement> result = new ArrayList<PathElement>( node.steps );
		while( node.fromNode != null ) {
			PathElement pathElement = new PathElement(
					node.fromPathX, node.fromPathY, node.fromPathIndex, node.fromDirection < 2
			);
			result.add( pathElement );
			node = node.fromNode;
		}
		return result;
	}

	
	private class Node implements Comparable<Node> {
		private int costSoFar;
		private int estimatedCostRemaining;
		private int gx, gy, gIndex;
		private Node fromNode;
		private int fromDirection;
		private int fromPathX;
		private int fromPathY;
		private int fromPathIndex;
		private int steps;
		
		public Node( 
				int costSoFar, 
				int estimatedCostRemaining,
				int gx, int gy, int gIndex 
		) {
			this.costSoFar = costSoFar;
			this.estimatedCostRemaining = estimatedCostRemaining;
			this.gx = gx;
			this.gy = gy;
			this.gIndex = gIndex;
		}
		
		public int getTotalEstimatedCost() {
			return this.costSoFar + this.estimatedCostRemaining;
		}
		
		public int hashCode() {
			return (gx << 16) + (gy << 4) + gIndex;
		}
		
		public boolean equals(Object o) {
			if( o != null && this.getClass().equals( o.getClass() ) ) {
				return equals( (Node)o );
			} else {
				return false;
			}
		}
		
		public boolean equals( Node o ) {
			return gx == o.gx && gy == o.gy && gIndex == o.gIndex;
		}

		public int compareTo(Node o) {
			return o.getTotalEstimatedCost() - getTotalEstimatedCost();
		}
	}
}
